This invention relates to digital communications, and more particularly to a method of managing a circular buffer.
Circular buffers are used in many applications where, for example, data may arrive at a varying rate and need to be read out at a constant rate. A particular application of circular buffers is in ATM circuit emulation services, where cells carrying constant bit rate data arrive at varying times determined by CDV (Cell Delay Variation), and the data contained in the cells has to be read out onto a TDM bus at a constant rate.
In a circular buffer, it is of course possible for the incoming data to get too far ahead of the reading of the outgoing data for the size of the buffer, in which case unread data will be overwritten by new data and an xe2x80x9coverrunxe2x80x9d will occur. Similarly, if the new data arrives at an insufficient rate to replenish the data in the buffer, the read-pointer will re-read old data, and in this case an xe2x80x9cunderrunxe2x80x9d occurs. It is important to be able to identify buffer underruns and overruns.
Mitel Corporation makes a SAR (Segmentation and Reassembly) device sold under product number MT90500 for creating TDM data streams from incoming ATM cells, which are written into circular buffers (one for each TDM channel). A single-bit flag in the data circular buffer is used to indicate whether the data in a memory location has been read. This bit is cleared upon data writes and is set (written to xe2x80x981xe2x80x99) after the data is read, to indicate that the data has been read.
Additionally, the MT90500 and other devices overwrite the circular buffer data itself with FFh (or some other pre-specified pattern) to indicate that the data has been read.
U.S. Pat. No. 5,584,038 discloses a method of using wrap bits in a circular buffer to indicate whether a queue of the circular buffer has been traversed.
U.S. Pat. No. 5,978,868 discloses a system for generating buffer status flags by comparing read and write pointers and determining direction of progression of a read-pointer with respect to a write pointer.
An object of the present invention is to permit the identification of read underruns without the need for semaphore flags.
According to the present invention there is provided a method of managing a circular buffer, comprising writing data into said circular buffer at an address pointed to by a write pointer, and writing into said address a first number that increments modulo a predetermined number each time said circular buffer is traversed by the write pointer.
The number is preferably in the form of a most significant bits (MSB) extension of the write pointer. It typically consists of two extra bits, which permit four distinct rotations 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, etc. These two extra bits are written into the circular buffer alongside the circular buffer data. The two extra bits are called xe2x80x9cturnsxe2x80x9d. The number could also consist of a single bit.
A similar number is incremented each time the read pointer traverses the circular buffer. When data is read from the circular buffer, the number associated with the read pointer is compared to the number associated with the data in the buffer. This enables the validity of the data to be checked (i.e., to determine whether or not an underrun has occurred). Typically, the number associated with the read pointer is also in the form of an extension to the read pointer, typically two extra most significant bits.
This technique permits the system to distinguish between a short-duration underrun and a long-duration underrun or between an overrun and an underrun by the magnitude of the difference in the xe2x80x9cturnsxe2x80x9d bits associated with the data in the buffer address being read and the read pointer.
In another aspect the invention provides a circular buffer comprising a plurality of address locations for storing data; a write pointer for pointing to an address in said circular buffer where incoming data is to be written; a read pointer for pointing to an address in said circular buffer from which data is to be read out; and each of said buffer addresses including a register portion storing a first number associated with said write pointer, said first number incrementing modulo a predetermined number each time said circular buffer is traversed by the write pointer.